#include<bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define fir first
#define sec second
using namespace std;
const ll N=2010,inf=0x3f3f3f3f3f3f3f3f;
int c,t,n,m;
ll dis[N],ans,sum;
ull val[N],temp;
vector<int>d[N],cnt,e[N];
bitset<N>vis[N];
unordered_map<ull,bool>ma;
void dij(int st){
    priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>qu;
    bitset<N>vis2;
    for(int i=1;i<=n;i++){
        dis[i]=inf;
    }
    dis[st]=0;
    qu.push({0,st});
    while(!qu.empty()){
        auto nw=qu.top();
        qu.pop();
        if(vis2[nw.sec])continue;
        vis2[nw.sec]=1;
        for(auto i:d[nw.sec]){
            if(vis2[i])continue;
            if(dis[nw.sec]+1<dis[i]){
                dis[i]=dis[nw.sec]+1;
                qu.push({dis[i],i});
            }
        }
    }
}
void calc(){
    ll res=0;
    for(auto i:cnt){
        dij(i);
        for(auto j:e[i]){
            if(dis[j]==inf)res=-inf;
            else res-=dis[j];
        }
    }
    if(res>ans){
        ans=res;
        sum=0;
    }
    if(res==ans){
        sum++;
    }
}
void dfs(int nw){
    if(nw==m){
        if(ma.count(temp))return;
        else ma[temp]=1;
        calc();
        return;
    }
    for(int i=1;i<=n;i++){
        for(int j=i+1;j<=n;j++){
            if(vis[i][j])continue;
            vis[i][j]=1;
            d[i].push_back(j);
            d[j].push_back(i);
            temp+=val[i]*val[j];
            dfs(nw+1);
            temp-=val[i]*val[j];
            vis[i][j]=0;
            d[i].pop_back();
            d[j].pop_back();
        }
    }
}
void solve(){
    cin>>n>>m;
    mt19937_64 sj(random_device{}());
    cnt.clear();
    ma.clear();
    for(int i=1;i<=n;i++){
        e[i].clear();
        val[i]=sj();
    }
    for(int i=1;i<=m;i++){
        int a,b;
        cin>>a>>b;
        cnt.push_back(a);
        e[a].push_back(b);
    }
    if(3<=c&&c<=4){
        cout<<-(n-1)*2<<' '<<0<<'\n';
        return;
    }
    sort(cnt.begin(),cnt.end());
    cnt.resize(unique(cnt.begin(),cnt.end())-cnt.begin());
    ans=-inf;
    sum=0;
    dfs(1);
    cout<<ans<<' '<<sum<<'\n';
}
int main(){
    freopen("oi.in","r",stdin);
    freopen("oi.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(nullptr);
    cin>>c>>t;
    while(t--){
        solve();
    }
    return 0;
}